//
//  ViewController.swift
//  纯函数式数据结构（二叉树搜索）
//
//  Created by 崔博 on 2017/7/19.
//  Copyright © 2017年 崔博. All rights reserved.
//

// 定义可递归的枚举
// 设计一种无序集合.
// 1.empty 返回一个空的无序集合
// 2.isEmpty 检查一个无序集合是否为空
// 3.contains 检查无序集合中是否包含某个元素
// 4.insert 向无序集合插入一个元素
indirect enum BinarySearchTree<Element: Comparable> {
    
    case Leaf
    case Node(BinarySearchTree<Element>,Element, BinarySearchTree<Element>)
}
import UIKit


class ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
       
        // 手动造🌲
        let leaf: BinarySearchTree<Int> = .Leaf
        let five: BinarySearchTree<Int> = .Node(leaf,5,leaf)
        
    }
    
    // 最先想到的是数组 易如反掌： 但是数组是线性的 无序集合过大的时候 性能就会出现问题
    func empty<Element>() -> [Element] {
        return []
    }
    
    func isEmpty<Element>(set: [Element]) -> Bool {
        return set.isEmpty
    }
    
    func contanis<Element: Equatable>(x: Element,_ set: [Element]) -> Bool {
        return set.contains(x)
    }
    
    func insert<Element: Equatable>(x: Element, _ set: [Element]) -> [Element] {
        return contanis(x: x, set) ? set : [x] + set
    }
}
extension BinarySearchTree {
    
    init() {
        self = .Leaf
    }
    init(_ value: Element) {
        self = .Node(.Leaf, value, .Leaf)
    }
    var count: Int  {
        
        switch self {
        case .Leaf:
            return 0
        case let .Node(left,_, right):
            return 1 + left.count + right.count
        }
    }
    var elements: [Element] {
        switch self {
        case .Leaf:
            return[]
        case let .Node(left, x, right):
            return left.elements + [x] + right.elements
        }
    }
    var isEmpty: Bool{
        if  case .Leaf = self {
            return true
        }else{
            return false
        }
    }
}
extension BinarySearchTree where Element: Comparable{
    
    var isBST: Bool{
        switch self {
        case .Leaf:
            return true
        case let .Node.elements.all { }
        }
    }
}
extension LazySequenceProtocol{
    func  all(predicate: Generator.Element) -> Bool {
        for x in self where !predicate(x) {
            return false
        }
        return true
    }
}
